package com.tsx.leetcode.hot100.other;

import java.util.*;

public class KSmallestSubsequenceSums {
    public static List<Integer> findKSmallestSubsequenceSums(int[] arr, int k) {
        // 使用集合来存储所有可能的子序列累加和
        Set<Integer> sums = new HashSet<>();
        sums.add(0);  // 空子序列的和为 0
        
        // 生成所有可能的子序列累加和
        for (int num : arr) {
            Set<Integer> newSums = new HashSet<>();
            for (int sum : sums) {
                newSums.add(sum + num);
            }
            sums.addAll(newSums);
        }
        
        PriorityQueue<Integer> queue = new PriorityQueue<>(sums);
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < k && !queue.isEmpty(); i++) {
            result.add(queue.poll());
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int k = 4;
        List<Integer> results = findKSmallestSubsequenceSums(arr, k);
        System.out.println(results);  // 应该打印 [0, 1, 2, 3]
    }
}
